package leetCode.q200;

public class UnionSet {
    class UnionFind {
        int count;//集的数量
        int[] parent;
        int[] rank;

        /**
         * 并查集的创建函数
         * @param grid
         */
        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];
            rank = new int[m * n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {
                        //让代表等于自己
                        parent[i * n + j] = i * n + j;
                        ++count;
                    }
                    rank[i * n + j] = 0;
                }
            }
        }

        /**
         * 并查集 查找元素i的上级
         * @param i
         * @return
         */
        public int find(int i) {// 找到 i 的代表
            if (parent[i] != i) parent[i] = find(parent[i]);
            return parent[i];
        }

        /**
         * 并查集合并两个元素
         * @param x
         * @param y
         */
        public void union(int x, int y) {//将xy两个集合并
            int rootx = find(x);
            int rooty = find(y);
            if (rootx != rooty) {
                /**
                 * 如果x的级别高，令y的上级为x
                 * 如果y的级别高，令x的上级为y
                 * 如果相等让y的上级为x，x的级别加1
                 */
                if (rank[rootx] > rank[rooty]) {
                    parent[rooty] = rootx;
                } else if (rank[rootx] < rank[rooty]) {
                    parent[rootx] = rooty;
                } else {
                    parent[rooty] = rootx;
                    rank[rootx] += 1;
                }
                --count;
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
//        int num_islands = 0;
        UnionFind uf = new UnionFind(grid);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    if (i - 1 >= 0 && grid[i-1][j] == '1') {
                        uf.union(i * n + j, (i-1) * n + j);
                    }
                    if (i + 1 < m && grid[i+1][j] == '1') {
                        uf.union(i * n + j, (i+1) * n + j);
                    }
                    if (j - 1 >= 0 && grid[i][j-1] == '1') {
                        uf.union(i * n + j, i * n + j - 1);
                    }
                    if (j + 1 < n && grid[i][j+1] == '1') {
                        uf.union(i * n + j, i * n + j + 1);
                    }
                }
            }
        }

        return uf.getCount();
    }
}
